class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class BuildTree2 {
    public int postIndex;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length-1;
        return buildTreeChild(postorder, inorder ,0 , inorder.length-1);
    }


    private TreeNode buildTreeChild(int[] postorder, int[] inorder,int inBegin,int inEnd) {
        if (inBegin > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postIndex]);
        int rootIndex = findIndex(inorder, inBegin, inEnd, postorder[postIndex]);
        postIndex--;


        root.right = buildTreeChild(postorder, inorder, rootIndex+1, inEnd);
        root.left = buildTreeChild(postorder, inorder, inBegin, rootIndex-1);
        return root;
    }


    private int findIndex(int[] inorder, int inBegin, int inEnd, int key) {
        for(int i = inBegin; i <= inEnd; i++) {
            if (inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
}
